/*
 * @(#)XfdmIncGrid.java        1.0 2000/05/09
 *
 * This file is part of Xfuzzy 3.0, a design environment for fuzzy logic
 * based systems.
 *
 * (c) 2000 IMSE-CNM. The authors may be contacted by the email address:
 *                    xfuzzy-team@imse.cnm.es
 *
 * Xfuzzy is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation.
 *
 * Xfuzzy is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 */

package xfuzzy.xfdm.model.algorithm;

import xfuzzy.lang.*;
import xfuzzy.xfdm.model.XfdmAlgorithm;
import xfuzzy.xfdm.model.XfdmConfig;
import xfuzzy.xfdm.model.XfdmInputStyle;
import xfuzzy.xfdm.model.XfdmSystemStyle;
import xfuzzy.xfsl.model.*;
import xfuzzy.xfds.XfdsDataSet;

/**
 * Algoritmo de particion incremental
 * 
 * @author Francisco Jos� Moreno Velo
 *
 */
public class XfdmIncGrid extends XfdmAlgorithm {

	//----------------------------------------------------------------------------//
	//                            MIEMBROS PRIVADOS                               //
	//----------------------------------------------------------------------------//

	/**
	 * N�mero m�ximo de funciones de pertenencia
	 */
	private int mfs_limit;
	
	/**
	 * N�mero m�ximo de reglas
	 */
	private int rule_limit;
	
	/**
	 * Valor l�mite del RMSE
	 */
	private double rmse_limit;
	
	/**
	 * Marcador que indica si hay que ajustar la partici�n cada vez que se
	 * a�ade un nuevo punto
	 */
	private boolean learning;

	/**
	 * Puntos creados en el espacio de entrada
	 */
	private double input[][];
	
	/**
	 * Puntos creados en el espacio de salida
	 */
	private double output[][];
	
	/**
	 * RMSE tras el �ltimo punto
	 */
	private double last_rmse;
	
	/**
	 * �ndice de la peor instancia
	 */
	private int worst_pattern;

	//----------------------------------------------------------------------------//
	//                                CONSTRUCTOR                                 //
	//----------------------------------------------------------------------------//

	/**
	 * Constructor por defecto
	 */
	public XfdmIncGrid() {
		this.mfs_limit = -1;
		this.rule_limit = -1;
		this.rmse_limit = -1;
		this.learning = false;
	}

	/**
	 * Constructor desde la interfaz gr�fica
	 */
	public XfdmIncGrid(int mfs, int rule, double rmse, boolean learn) {
		this.mfs_limit = mfs;
		this.rule_limit = rule;
		this.rmse_limit = rmse;
		this.learning = learn;
	}

	/**
	 * Constructor desde el fichero de configuraci�n
	 */
	public XfdmIncGrid(double[] param) {
		this.mfs_limit = (int) param[0];
		this.rule_limit = (int) param[1];
		this.rmse_limit = (double) param[2];
		this.learning = (((int) param[3]) == 1);
	}

	//----------------------------------------------------------------------------//
	//                             M�TODOS P�BLICOS                               //
	//----------------------------------------------------------------------------//

	//----------------------------------------------------------------------------//
	// M�todos de acceso a la configuraci�n	                                      //
	//----------------------------------------------------------------------------//

	/**
	 * Obtiene el valor del m�ximo n�mero de MFs permitido
	 */
	public int getMfsLimit() {
		return this.mfs_limit;
	}

	/**
	 * Asigna el valor del m�ximo n�mero de MFs permitido
	 */
	public void setMfsLimit(int limit) {
		this.mfs_limit = limit;
	}

	/**
	 * Obtiene el valor del m�ximo n�mero de reglas permitido
	 */
	public int getRuleLimit() {
		return this.rule_limit;
	}

	/**
	 * Asigna el valor del m�ximo n�mero de reglas permitido
	 */
	public void setRuleLimit(int limit) {
		this.rule_limit = limit;
	}

	/**
	 * Obtiene el valor de la m�nima desviaci�n permitida 
	 */
	public double getRMSELimit() {
		return this.rmse_limit;
	}

	/**
	 * Asigna el valor de la m�nima desviaci�n permitida
	 */
	public void setRMSELimit(double limit) {
		this.rmse_limit = limit;
	}

	/**
	 * Obtiene el valor de la opci�n de aprendizaje
	 */
	public boolean isLearning() {
		return this.learning;
	}

	/**
	 * Asigna el valor de la opci�n de aprendizaje
	 */
	public void setLearning(boolean learn) {
		this.learning = learn;
	}

	//----------------------------------------------------------------------------//
	// M�todos de desarrollo de XfdmAlgorithm                                     //
	//----------------------------------------------------------------------------//

	/**
	 * Obtiene un duplicado del objeto
	 */
	public Object clone() {
		return new XfdmIncGrid(mfs_limit,rule_limit,rmse_limit,learning);
	}

	/**
	 * Obtiene el nombre del algoritmo
	 */
	public String toString() {
		return "Incremental Grid Partition";
	}

	/**
	 * Representaci�n en el fichero de configuraci�n
	 */
	public String toXML() {
		String lrn = (learning? "1": "0");
		String eol = System.getProperty("line.separator", "\n");
		String code = "\t\t<algorithm name=\"IncGrid\" >"+eol;
		code += "\t\t\t<param name=\"mfs\" value=\""+mfs_limit+"\" ></param>"+eol;
		code += "\t\t\t<param name=\"rules\" value=\""+rule_limit+"\" ></param>"+eol;
		code += "\t\t\t<param name=\"rmse\" value=\""+rmse_limit+"\" ></param>"+eol;
		code += "\t\t\t<param name=\"learning\" value=\""+lrn+"\" ></param>"+eol;
		code +=	"\t\t</algorithm>";
		return code;
	}

	/**
	 * Obtiene el tipo de base de conocimiento que genera el algoritmo
	 */
	public int getKnowledgeBaseKind() {
		return KnowledgeBase.RULE_SET;
	}

	/**
	 * Indica si el algoritmo necesita que las variables de entrada tengan creadas
	 * las funciones de pertenencia. En caso contrario el algoritmo debe encargarse
	 * de dar contenido a los tipos de las variables de entrada.
	 */
	public boolean needInputMemFuncs() {
		return false;
	}
	
	/**
	 * Indica si el algoritmo necesita que las variables de salida tengan creadas
	 * las funciones de pertenencia. En caso contrario el algoritmo debe encargarse
	 * de dar contenido a los tipos de las variables de salida.
	 */
	public boolean needOutputMemFuncs() {
		return false;
	}

	/**
	 * Indica si el algoritmo necesita que la estructura del sistema est� creada.
	 * Este requisito es propio de los algoritmo que contienen alguna etapa de
	 * optimizaci�n param�trica.
	 * @return
	 */
	public boolean needSystemStructure() {
		return true;
	}
		
	/**
	 * Indica si el algoritmo es v�lido para problemas de clasificaci�n
	 * @return
	 */
	public boolean supportsClassification() {
		return false;
	}
	
	/**
	 * Indica si el algoritmo es v�lido para problemas de regresi�n
	 * @return
	 */
	public boolean supportsRegression() {
		return true;
	}

	/**
	 * Genera el contenido de la base de conocimiento a partir de los datos
	 */
	public void extractKnowlegde(KnowledgeBase base, XfdmConfig config) {
		initInputPartition(base);
		initOutputPartition(config.getDataSet());
		createContent(base,config);
		if(learning) learning(config, base);
		computeError(config);
		while(!satisfyEndCondition(base)) {
			updatePartition(config.getDataSet());
			createContent(base,config);
			if(learning) learning(config,base);
			computeError(config);
		}
	}

	//----------------------------------------------------------------------------//
	//                             M�TODOS PRIVADOS                               //
	//----------------------------------------------------------------------------//

	//----------------------------------------------------------------------------//
	// Funciones que generan el contenido del sistema                             //
	//----------------------------------------------------------------------------//

	/**
	 * Genera el contenido del sistema a partir de la partici�n
	 */
	private void createContent(KnowledgeBase base, XfdmConfig config) {
		Variable[] ivar = base.getInputs();
		Variable[] ovar = base.getOutputs();
		XfdmInputStyle commonstyle = config.getCommonInputStyle();
		XfdmInputStyle[] inputstyle = config.getInputStyles();
		for(int i=0; i<ivar.length; i++) {
			int style = commonstyle.getStyle();
			if(inputstyle != null && inputstyle.length > i && inputstyle[i] != null) {
				style = inputstyle[i].getStyle();
			}
			if(style == XfdmInputStyle.FREE_TRIANGLES) {
				createFreeTriangles(ivar[i].getType(),input[i]);
			} else {
				createTriangularFamily(ivar[i].getType(),input[i]);
			}
		}

		if(config.getSystemStyle().getDefuzMethod() == XfdmSystemStyle.FUZZYMEAN) {
			for(int i=0; i<ovar.length; i++) {
				createSingletons(ovar[i].getType(),output[i]);
			}
		} else {
			for(int i=0; i<ovar.length; i++) createBells(ovar[i].getType(),output[i]);
		}

		createRules(base);
	}

	/**
	 * Genera el antecedente correspondiente a un punto de la partici�n
	 */
	private Relation createAntecedent(KnowledgeBase base, int[] index) {
		Variable ivar[] = base.getInputs();
		int is = Relation.IS;

		LinguisticLabel pmf[] = new LinguisticLabel[index.length];
		for(int i=0; i<index.length; i++) {
			pmf[i] = ivar[i].getType().getAllMembershipFunctions()[index[i]];
		}

		Relation rel = Relation.create(is,null,null,ivar[0],pmf[0],base);
		for(int j=1; j<index.length; j++) {
			Relation nrel = Relation.create(is,null,null,ivar[j],pmf[j],base);
			rel = Relation.create(Relation.AND,rel,nrel,null,null,base);
		}

		return rel;
	}

	/**
	 * Genera las reglas correspondientes a la partici�n
	 */
	private void createRules(KnowledgeBase base) {
		base.removeAllRules();
		int index[] = new int[input.length];
		Variable ovar[] = base.getOutputs();
		int count = computeNumberOfRules();
		for(int i=0; i<count; i++) {
			Rule rule = new Rule(createAntecedent(base,index));
			for(int j=0; j<ovar.length; j++) {
				LinguisticLabel pmf = ovar[j].getType().getAllMembershipFunctions()[i];
				rule.add(new Conclusion(ovar[j],pmf,base));
			}
			((RuleSet) base).addRule(rule);
			incrementIndex(index);
		}
	}

	/**
	 * Calcula el n�mero de reglas en funci�n de la partici�n
	 */
	private int computeNumberOfRules() {
		int number = 1;
		for(int i=0; i<input.length; i++) number = number*(input[i].length);
		return number;
	}

	//----------------------------------------------------------------------------//
	// Funciones que generan las funciones de pertenencia                         //
	//----------------------------------------------------------------------------//

	/**
	 * Crea una familia de tri�ngulos
	 */
	private void createTriangularFamily(Type type, double[] partition) {
		type.removeAllLabels();
		type.removeAllFamilies();
		double param[] = new double[partition.length-2];
		for(int i=0; i<param.length; i++) param[i] = partition[i+1];

		Family fam = new xfuzzy.pkg.xfl.family.triangular();
		fam.set("fam",type);
		try { fam.set(param); type.addFamily(fam); } catch(XflException ex) {}

		for(int i=0; i<fam.members(); i++) {
			FamiliarMemFunc fmf = new FamiliarMemFunc("mf"+i,fam,i);
			try { type.add(fmf); } catch(XflException e) {}
		}
	}

	/**
	 * Crea un conjunto de tri�ngulos equiespaciados
	 */
	private void createFreeTriangles(Type type, double[] partition) {
		type.removeAllLabels();
		type.removeAllFamilies();
		double param[] = new double[partition.length+2];
		param[0] = partition[0]-1;
		param[param.length-1] = partition[partition.length-1]+1;
		for(int i=0; i<partition.length; i++) param[i+1] = partition[i];

		Universe u = type.getUniverse();
		double pp[] = new double[3];

		for(int i=0; i<partition.length; i++) {
			pp[0] = param[i];
			pp[1] = param[i+1];
			pp[2] = param[i+2];
			ParamMemFunc pmf = new xfuzzy.pkg.xfl.mfunc.triangle();
			pmf.set("mf"+i,u);
			try { pmf.set(pp); type.add(pmf); } catch(XflException ex) {}
		}
	}

	/**
	 * Crea un conjunto de singularidades
	 */
	private void createSingletons(Type type, double[] value) {
		type.removeAllLabels();
		Universe u = type.getUniverse();
		for(int i=0; i<value.length; i++) {
			ParamMemFunc pmf = new xfuzzy.pkg.xfl.mfunc.singleton();
			pmf.set("mf"+i, u);
			pmf.set(value[i]);
			try { type.add(pmf); } catch(XflException e) {}
		}
	}

	/**
	 * Crea un conjunto de campanas
	 */
	private void createBells(Type type, double[] value) {
		type.removeAllLabels();
		Universe u = type.getUniverse();
		double min = u.min();
		double max = u.max();
		double param[] = new double[2];
		param[1] = (max - min)/10;
		for(int i=0; i<value.length; i++) {
			ParamMemFunc pmf = new xfuzzy.pkg.xfl.mfunc.bell();
			pmf.set("mf"+i, u);
			param[0] = value[i];
			try { pmf.set(param); type.add(pmf); } catch(XflException ex) {}
		}
	}

	//----------------------------------------------------------------------------//
	// Funciones que manejan las particiones                                      //
	//----------------------------------------------------------------------------//

	/**
	 * Crea la partici�n inicial de las entradas (con min y max)
	 */
	private void initInputPartition(KnowledgeBase base) {
		Variable[] ivar = base.getInputs();
		this.input = new double[ivar.length][2];
		for(int i=0; i<input.length; i++) {
			input[i][0] = ivar[i].getType().getUniverse().min();
			input[i][1] = ivar[i].getType().getUniverse().max();
		}
	}

	/**
	 * Crea los valores de salida de la partici�n inicial
	 */
	private void initOutputPartition(XfdsDataSet dataset) {
		int points = computeNumberOfRules();
		this.output = new double[dataset.getNumberOfOutputs()][points];
		int index[] = new int[input.length];
		for(int i=0; i<points; i++) {
			int pp = getPatternIndex(dataset, getPartitionFromIndexes(index) );
			for(int j=0; j<output.length; j++) output[j][i] = dataset.output[pp][j];
			incrementIndex(index);
		}
	}

	/**
	 * Incrementa un vector de �ndices sobre la partici�n
	 */
	private void incrementIndex(int[] index) {
		boolean overhead = true;
		int i = index.length-1;
		while(overhead && i>=0) {
			index[i]++;
			if(index[i]>=input[i].length) { index[i] = 0; i--; }
			else overhead = false;
		}
	}

	/**
	 * Obtiene un punto de la partici�n a partir de los �ndices
	 */
	private double[] getPartitionFromIndexes(int[] index) {
		double partition[] = new double[input.length];
		for(int i=0; i<input.length; i++) partition[i] = input[i][index[i]];
		return partition;
	}

	//----------------------------------------------------------------------------//
	// Funciones de b�squeda en los patrones                                      //
	//----------------------------------------------------------------------------//

	/**
	 * Busca el patr�n mas cercano a un punto del espacio de entrada
	 */
	private int getPatternIndex(XfdsDataSet dataset, double[] input) {
		int index = 0;
		double dist = patternDistance(dataset,0,input);
		for(int i=1; i<dataset.input.length; i++) {
			double nd = patternDistance(dataset,i,input);
			if(nd<dist) { dist = nd; index = i; }
		}
		return index;
	}

	/**
	 * Calcula la distancia de un patr�n a un punto del espacio de entrada
	 */
	private double patternDistance(XfdsDataSet dataset, int index, double[] input) {
		double dist = 0;
		for(int i=0; i<input.length; i++) {
			dist+=(dataset.input[index][i]-input[i])*(dataset.input[index][i]-input[i]); 
		}
		return dist;
	}

	//----------------------------------------------------------------------------//
	// Funciones de evaluaci�n del sistema                                        //
	//----------------------------------------------------------------------------//

	/**
	 * Verifica si se han cumplido las condiciones de t�rmino
	 */
	private boolean satisfyEndCondition(KnowledgeBase base) {
		if(rule_limit > 0 && ((RuleSet) base).getRules().length > rule_limit) return true;
		if(rmse_limit > 0 && last_rmse <= rmse_limit) return true;
		for(int i=0; i<input.length; i++) {
			if(mfs_limit > 0 && input[i].length > mfs_limit) return true;
		}
		if(worst_pattern < 0) return true;
		return false;
	}

	/**
	 * Calcula el error medio que comete el sistema y el patr�n en  el que la desviaci�n es mayor
	 */
	private void computeError(XfdmConfig config) {
		SystemModule system = config.getSpecification().getSystemModule();
		XfdsDataSet dataset = config.getDataSet();
		double mxae=0;
		double mse=0;
		int index = -1;
		for(int p=0; p<dataset.input.length; p++) {
			double[] out = system.crispInference(dataset.input[p]);
			for(int i=0; i<out.length; i++) {
				double dev = (out[i]-dataset.output[p][i])/dataset.range[i];
				if(dev<0) dev = -dev;
				mse += dev*dev/out.length;
				if(dev>mxae) { mxae = dev; index = p; }
			}
		}
		this.last_rmse = Math.sqrt(mse/dataset.input.length);

		int list[] = new int[0];
		while(!testNewPoint(dataset,index)) {
			int nl[] = new int[list.length+1];
			System.arraycopy(list,0,nl,0,list.length);
			nl[list.length] = index;
			list = nl;

			mxae = 0;
			index = -1;
			for(int p=0; p<dataset.input.length; p++) {
				boolean excluded = false;
				for(int l=0; l<list.length; l++) if(list[l] == p) excluded = true;
				if(excluded) continue;

				double[] out = system.crispInference(dataset.input[p]);
				for(int i=0; i<out.length; i++) {
					double dev = (out[i]-dataset.output[p][i])/dataset.range[i];
					if(dev<0) dev = -dev;
					if(dev>mxae) { mxae = dev; index = p; }
				}
			}
		}
		this.worst_pattern = index;
	}

	/**
	 * Estudia el punto a incluir
	 */
	private boolean testNewPoint(XfdsDataSet dataset, int pattern_index) {
		double newpoint[] = dataset.input[pattern_index];
		int position[] = new int[input.length];
		for(int i=0; i<input.length; i++) {
			double range = input[i][input[i].length-1] - input[i][0];
			int j;
			for(j=0; j<input[i].length; j++) if(input[i][j] > newpoint[i]) break;
			double prev = (j==0? input[i][0] : input[i][j-1]);
			double next = (j==input[i].length? input[i][j-1] : input[i][j]);
			boolean insert = true;
			if(newpoint[i]-prev < range/100) insert = false;
			if(next-newpoint[i] < range/100) insert = false;
			if(insert) position[i] = j; else position[i] = -1;
		}

		for(int i=0; i<position.length; i++) if(position[i] != -1) return true;
		return false;
	}

	/**
	 * Actualiza la partici�n
	 */
	private void updatePartition(XfdsDataSet dataset) {
		if(worst_pattern < 0) return;
		double newpoint[] = dataset.input[worst_pattern];
		int position[] = new int[input.length];
		for(int i=0; i<input.length; i++) {
			double range = input[i][input[i].length-1] - input[i][0];
			int j;
			for(j=0; j<input[i].length; j++) if(input[i][j] > newpoint[i]) break;
			double prev = (j==0? input[i][0] : input[i][j-1]);
			double next = (j==input[i].length? input[i][j-1] : input[i][j]);
			boolean insert = true;
			if(newpoint[i]-prev < range/100) insert = false;
			if(next-newpoint[i] < range/100) insert = false;
			if(insert) {
				double ni[] = new double[input[i].length+1];
				System.arraycopy(input[i],0,ni,0,j);
				ni[j] = newpoint[i];
				System.arraycopy(input[i],j,ni,j+1,input[i].length-j);
				input[i] = ni;
				position[i] = j;
			} else position[i] = -1;
		}

		int old=0;
		int index[] = new int[input.length];
		int count = computeNumberOfRules();
		double no[][] = new double[dataset.getNumberOfOutputs()][count];
		for(int i=0; i<count; i++) {
			boolean newvalue = false;
			for(int j=0; j<index.length; j++) if(index[j] == position[j]) newvalue=true;
			if(!newvalue) {
				for(int j=0; j<no.length; j++) no[j][i] = output[j][old];
				old++;
			} else {
				int pp = getPatternIndex( dataset, getPartitionFromIndexes(index) );
				for(int j=0; j<no.length; j++) no[j][i] = dataset.output[pp][j];
			}
			incrementIndex(index);
		}

		output = no;
	}

	/**
	 * Ajusta las salidas del sistema con el algoritmo de Marquardt-Levenberg
	 */
	private void learning(XfdmConfig config, KnowledgeBase base) {
		Variable[] ovar = base.getOutputs();
		double param[] = { 0.1, 10.0, 0.1};
		int alg = XfslAlgorithm.MARQUARDT;
		int err = XfslErrorFunction.MEAN_SQUARE_ERROR;
		int end = XfslEndCondition.TRN_VAR;
		XfslConfig xfslconfig = new XfslConfig();
		try { 
			xfslconfig.trainingfile = config.getDataSetFile();
			xfslconfig.algorithm = XfslAlgorithmFactory.createAlgorithm(alg,param);
			xfslconfig.errorfunction = new XfslErrorFunction(err);
			xfslconfig.endcondition.setLimit(end,0.001);
			xfslconfig.addSetting("ANY.ANY.ANY",false);
			for(int i=0; i<ovar.length; i++) {
				xfslconfig.addSetting(ovar[i].getType().getName()+".ANY.ANY",true);
			}
			XfslThread lrnthread = new XfslThread(config.getSpecification(),xfslconfig);
			lrnthread.run();
		} catch (Exception ex) { }
		for(int i=0; i<ovar.length; i++) {
			LinguisticLabel label[] = ovar[i].getType().getAllMembershipFunctions();
			for(int j=0; j<label.length; j++) {
				this.output[i][j] = label[j].get()[0];
			}
		}
	}
}

